# 相交链表：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/submissions/

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# 最简单的方法是 集合，存储headA， 看B中节点是否有在其中的
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        """
            使用集合来存储遍历后的节点，看是否有相等
        """
        nodeSet = set()
        p1 = headA
        p2 = headB

        while p1:
            nodeSet.add(p1)
            p1 = p1.next

        while p2:
            if p2 in nodeSet:
                return p2
            p2 = p2.next
        
        return None


# 利用走的路程相等
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        """
           双指针， 解法比较妙了， 看题解
        """
        p1 = headA
        p2 = headB
        # 有一个为 None， 则不可能存在交点
        if not headA or not headB:
            return None

        while p1 is not p2:
            if not p1:
                p1 = headB
            else:
                p1 = p1.next
            
            if not p2:
                p2 = headA
            else:
                p2 = p2.next
        
        return p1 if p1 else None


# 优化 if else 
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        """
           双指针， 解法比较妙了， 看题解
        """
        p1 = headA
        p2 = headB
        # 有一个为 None， 则不可能存在交点
        if not headA or not headB:
            return None

        while p1 is not p2:
            p1 = p1.next if p1 else headB
            p2 = p2.next if p2 else headA
        
        return p1 if p1 else None
        
